﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Schemes;
using Algoritmia.StateSpaces;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.HamiltonianCycle.Forward
{
    public class HamiltonianCycleStateSpace<TVertex> : IForwardStateSpace<DataStructures.Lists.IList<TVertex>,TVertex>
    {
        private readonly IDigraph<TVertex> _g;
        private readonly Func<IEnumerable<TVertex>, DataStructures.Lists.IList<TVertex>> _copyList;

        public HamiltonianCycleStateSpace(IDigraph<TVertex> G, Func<IEnumerable<TVertex>,DataStructures.Lists.IList<TVertex>> copyList = null)
        {
            _g = G;
            _copyList = copyList ?? (it => AlgoritmiaFactory.Lists<TVertex>.BuildDefault(it));
        }

        #region Implementation of IForwardStateSpace<IList<TVertex>,TVertex>

        public DataStructures.Lists.IList<TVertex> Decide(DataStructures.Lists.IList<TVertex> state, TVertex decision)
        {
            var newState = _copyList(state);
            newState.Add(decision);
            return newState;
        }

        public IEnumerable<TVertex> Decisions(DataStructures.Lists.IList<TVertex> state)
        {
            if (state.Count < _g.V.Count)
            {
                foreach (var vertex in _g.Successors(state.Last()))
                {
                    if (!state.Contains(vertex))
                    {
                        yield return vertex;
                    }
                }
            }
        }

        public IEnumerable<DataStructures.Lists.IList<TVertex>> InitialStates
        {
            get { yield return _copyList( new[] {_g.V.First()}); }
        }

        public bool IsFinal(DataStructures.Lists.IList<TVertex> state)
        {
            return _g.V.All(state.Contains) &&
                   _g.E.Contains(new Tuple<TVertex, TVertex>(state[state.Count - 1], state[0]));
        }

        #endregion
    }

    public class HamiltonianCycleSolver<T>
    {
        private readonly BacktrackingEnumerator<DataStructures.Lists.IList<T>, T, DataStructures.Lists.IList<T>> _enumerator;

        public HamiltonianCycleSolver()
        {
            _enumerator = new BacktrackingEnumerator<DataStructures.Lists.IList<T>, T, DataStructures.Lists.IList<T>>((space, i, d, f) =>
                                                                                            {
                                                                                                var list =
                                                                                                    AlgoritmiaFactory.Lists<T>.Default;
                                                                                                foreach(var e in i.Concat(d))
                                                                                                {
                                                                                                  list.Add(e);   
                                                                                                }
                                                                                                return list;
                                                                                            });
        }

        public DataStructures.Lists.IList<T> Solve(IDigraph<T> graph)
        {
            var stateSpace = new HamiltonianCycleStateSpace<T>(graph);
            return _enumerator.First(stateSpace);
        }
        
        public IEnumerable<DataStructures.Lists.IList<T>> SolveAll(IDigraph<T> graph)
        {
            var stateSpace = new HamiltonianCycleStateSpace<T>(graph);
            return _enumerator.Enumerate(stateSpace);
        }

    }
}
